package com.lw.leetcode.arr.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1508. 子数组和排序后的区间和
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/13 21:25
 */
public class RangeSum {

    public int rangeSum(int[] nums, int n, int left, int right) {
        int sumsLength = n * (n + 1) / 2;
        int[] sums = new int[sumsLength];
        int index = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                sums[index++] = sum;
            }
        }
        Arrays.sort(sums);
        int ans = 0;
        for (int i = left - 1; i < right; i++) {
            ans = (ans + sums[i]) % 1000000007;
        }
        return ans;
    }

}
